package cn.bellychang.bobo.queue.loop;

import cn.bellychang.bobo.arraylist.Iterator;
import cn.bellychang.bobo.queue.Queue;

/**
 * @author ChangLiang
 * @date 2020/9/8
 */
public class ArrayLoopQueue<E> implements Queue<E> {

    ArrayList<E> arrayList = new ArrayList<>();

    @Override
    public int getSize() {
        return arrayList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return arrayList.getSize() == 0;
    }

    @Override
    public void enqueue(E e) {
        arrayList.addLast(e);
    }

    @Override
    public E dequeue() {
        return arrayList.removeFirst();
    }

    @Override
    public E getFront() {
        return arrayList.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Queue Head {");
        Iterator<E> iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            builder.append(iterator.next());
            if (iterator.hasNext()) {
                builder.append("<-");
            }
        }
        return builder.append("} Tail").toString();
    }

    class ArrayList<E> {

        private E[] array;

        private static final int INIT_CAPACITY = 4;

        private static final int RESIZE_FACTOR = 2;

        private static final int REDUCE_FACTOR = 4;

        public ArrayList() {
            this(INIT_CAPACITY);
        }

        @SuppressWarnings("unchecked")
        public ArrayList(int capacity) {
            array = (E[]) new Object[capacity];
        }

        /**
         * head代表第一个元素所在的index，即下一个要取的位置
         */
        private int head = 0;

        /**
         * tail代表下一个要插入的index
         */
        private int tail = 0;

        private int size = 0;

        public int getCapacity() {
            return array.length;
        }

        public int getSize() {
            return this.size;
        }

        public void addLast(E e) {
            checkExtendRange();
            // tail到了尾部 并且 没有满 没有满已经在checkExtendRange中表达了
            // tail 代表下一个要放到位置 tail 最大就等于this.getCapacity - 1
            if (tail >= this.getCapacity()) {
                tail = 0;
            }
            array[tail++] = e;

            // array[tail] = e
            // tail = (tail + 1) % this.getCapacity() 代表了下一个要放的位置

            size++;
        }

        public E removeFirst() {
            checkEmpty();
            checkReduceRange();
            E e = array[head++];
            // head到了尾部
            if (head >= this.getCapacity()) {
                head = 0;
            }

            // E current = array[head];
            // // loitering object != memory leak
            // array[head] = null;
            // head = (head+1) % this.getCapacity()

            size--;
            return e;
        }

        public E getFirst() {
            checkEmpty();
            return array[head];
        }

        private void checkEmpty() {
            if (this.getSize() == 0) {
                throw new RuntimeException("array is empty");
            }
        }

        @SuppressWarnings("unchecked")
        private void checkExtendRange() {
            if (this.getSize() == this.getCapacity()) {
                E[] newArray = (E[]) new Object[this.getCapacity() * RESIZE_FACTOR];
                copyToNewArray(newArray);
            }
        }

        @SuppressWarnings("unchecked")
        private void checkReduceRange() {
            if (this.getCapacity() > INIT_CAPACITY && this.getSize() * REDUCE_FACTOR < this.getCapacity()) {
                E[] newArray = (E[]) new Object[this.getCapacity() / 4];
                copyToNewArray(newArray);
            }
        }

        private void copyToNewArray(E[] newArray) {
            int sizeTemp = this.getSize();
            if (head <= tail) {
                int j = 0;
                for (int i = head; i < this.getSize(); i++) {
                    newArray[j++] = array[i];
                }
            } else {
                int j = 0;
                for (int i = head; i <= tail + this.getCapacity(); i++) {
                    newArray[j++] = array[i % this.getCapacity()];
                }
            }
            array = newArray;
            head = 0;
            tail = sizeTemp;
        }

        public Iterator<E> iterator() {
            return new Iterator<E>() {

                int index = head;

                int count;

                @Override
                public boolean hasNext() {
                    return count < getSize() && getSize() > 0;
                }

                @Override
                public E next() {
                    count++;
                    E e = array[index];
                    index = (index + 1) % array.length;
                    return e;
                }
            };
        }
    }

}
